#pragma once

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <limits>
#include <memory>
#include <utility>

#include "ezstl_allocator.hpp"
#include "ezstl_construct.hpp"

namespace ezstl {

template <typename T, typename Allocator = Allocator<T>>
class Vector {
 public:
  using value_type = T;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using reference = value_type &;
  using const_reference = const value_type &;
  using pointer = value_type *;
  using const_pointer = const value_type *;
  using iterator = value_type *;
  using const_iterator = const value_type *;

 public:
  void show() const {
    for (const value_type &val : *this) {
      std::cout << val << " ";
    }
    std::cout << std::endl;
    std::cout << "size: " << size() << ", capacity: " << capacity()
              << std::endl;
  }

  Vector &operator=(const Vector &other) {
    if (this == &other) return *this;
    if (capacity() < other.size()) {
      Vector tmp(other);
      tmp.swap(*this);
      // this->swap(tmp);
    } else {
      // std::destroy(begin(), end());
      ezstl::destroy(begin(), end());
      // deallocate(m_start, capacity()); // TODO:
      m_finish = std::uninitialized_copy(other.begin(), other.end(), m_start);
    }
    return *this;
  }
  Vector &operator=(Vector &&other) {
    if (this == &other) return *this;
    // std::destroy(begin(), end());
    ezstl::destroy(begin(), end());
    deallocate(m_start, capacity());
    m_start = other.m_start;
    m_finish = other.m_finish;
    m_end_of_storage = other.m_end_of_storage;

    other.m_start = other.m_finish = other.m_end_of_storage = nullptr;
    return *this;
  }

  void assign(size_type count, const T &value);
  template <typename InputIt>
  void assign(InputIt first, InputIt last);

  // Constructor
  Vector() : m_start(nullptr), m_finish(nullptr), m_end_of_storage(nullptr) {}
  Vector(size_type count) {
    m_start = allocate(count);
    m_finish = m_end_of_storage = m_start + count;
  }
  Vector(size_type count, const value_type &value)
      : Vector(count) {
    // fill_n call operator=(const &) 用于修改已存在的对象
    // uninitialized_fill_n call placement new 用于在原始内存上创建新对象
    m_finish = m_end_of_storage =
        std::uninitialized_fill_n(m_start, count, value);
  }
  template <typename InputIt>
  Vector(InputIt first, InputIt last) {
    size_type count = std::distance(first, last);
    m_start = allocate(count);
    m_finish = m_end_of_storage = std::uninitialized_copy(first, last, m_start);
  }
  Vector(const Vector &other) : Vector(other.size()) {
    m_finish = m_end_of_storage =
        std::uninitialized_copy(other.begin(), other.end(), m_start);
  }
  Vector(Vector &&other) {
    m_start = other.m_start;
    m_finish = other.m_finish;
    m_end_of_storage = other.m_end_of_storage;

    other.m_start = other.m_finish = other.m_end_of_storage = nullptr;
  }

  // Destructor
  ~Vector() {
    // std::destroy(begin(), end());
    ezstl::destroy(begin(), end());
    deallocate(m_start, capacity());
  }

  // Element access
  reference at(size_type pos) { return m_start[pos]; }
  const_reference at(size_type pos) const { return m_start[pos]; }
  reference operator[](size_type pos) { return *(begin() + pos); }
  const_reference operator[](size_type pos) const { return *(begin() + pos); }
  reference front() { return *begin(); }
  const_reference front() const { return *begin(); }
  reference back() { return *(end() - 1); }
  const_reference back() const { return *(end() - 1); }
  T *data() { return begin(); }
  const T *data() const { return begin(); }

  // Iterators
  iterator begin() { return m_start; }
  const_iterator begin() const { return m_start; }
  const_iterator cbegin() const { return m_start; }
  iterator end() { return m_finish; }
  const_iterator end() const { return m_finish; }
  const_iterator cend() const { return m_finish; }

  // Capacity
  bool empty() const { /* return size() == 0; */ return begin() == end(); }
  size_type size() const { return m_finish - m_start; }
  size_type max_size() const {
    return std::numeric_limits<difference_type>::max();
  }
  void reserve(size_type new_cap) {
    if (new_cap <= capacity()) return;
    iterator new_start = allocate(new_cap);
    iterator new_finish = std::uninitialized_copy(begin(), end(), new_start);
    // std::destroy(begin(), end());
    ezstl::destroy(begin(), end());
    deallocate(m_start, capacity());
    m_start = new_start;
    m_finish = new_finish;
    m_end_of_storage = m_start + new_cap;
  }
  size_type capacity() const { return m_end_of_storage - m_start; }

  // Modifiers
  void clear() {
    // std::destroy(begin(), end());
    ezstl::destroy(begin(), end());
    m_finish = m_start;
  }
  iterator insert(const_iterator pos, const value_type &value) {
    return insert(pos, 1, value);
  }
  iterator insert(const_iterator pos, value_type &&value) {
    iterator non_k_pos = const_cast<iterator>(pos);
    difference_type offset = pos - cbegin();
    if (m_finish != m_end_of_storage) {
      if (pos != m_finish) {
        new (m_finish) value_type{std::move(*(m_finish - 1))};
        std::move_backward(non_k_pos, m_finish - 1, m_finish);
        *non_k_pos = std::move(value);
        ++m_finish;
      } else {
        new (m_finish) value_type{std::move(value)};
        ++m_finish;
      }
    } else {
      size_type new_size = std::max(2 * size(), size() + 1);
      iterator new_start = allocate(new_size);
      iterator new_finish =
          std::uninitialized_move(m_start, non_k_pos, new_start);
      new (new_finish) value_type{std::move(value)};
      new_finish++;
      std::uninitialized_move(non_k_pos, m_finish, new_finish);
      // std::destroy(begin(), end());
      ezstl::destroy(begin(), end());
      deallocate(m_start, capacity());
      m_start = new_start;
      m_finish = new_finish;
      m_end_of_storage = m_start + new_size;
    }
    return begin() + offset;
  }
  iterator insert(const_iterator pos, size_type count,
                  const value_type &value) {
    iterator non_k_pos = const_cast<iterator>(pos);
    if (count == 0) return non_k_pos;
    difference_type offset = pos - cbegin();
    if (capacity() - size() >= count) {
      const size_type elems_after = end() - non_k_pos;
      if (elems_after > count) {
        std::uninitialized_move(m_finish - count, m_finish, m_finish);
        std::move_backward(non_k_pos, m_finish - count, m_finish);
        std::fill(non_k_pos, non_k_pos + count, value);
        m_finish += count;
        // return non_k_pos;
      } else {
        std::uninitialized_move(non_k_pos, m_finish, non_k_pos + count);
        std::fill(non_k_pos, m_finish, value);
        std::uninitialized_fill(m_finish, non_k_pos + count, value);
        m_finish += count;
        // return non_k_pos;
      }
    } else {
      size_type new_size = std::max(2 * size(), size() + count);
      iterator new_start = allocate(new_size);
      iterator new_finish =
          std::uninitialized_move(m_start, non_k_pos, new_start);
      new_finish = std::uninitialized_fill_n(new_finish, count, value);
      new_finish = std::uninitialized_move(non_k_pos, m_finish, new_finish);
      // std::destroy(begin(), end());
      ezstl::destroy(begin(), end());
      deallocate(m_start, capacity());
      m_start = new_start;
      m_finish = new_finish;
      m_end_of_storage = m_start + new_size;
      // return m_start + elems_befor;
    }
    return begin() + offset;
  }
  // template <typename InputIt>
  // iterator insert(iterator pos, InputIt first, InputIt last);
  template <typename... Args>
  iterator emplace(const_iterator pos, Args &&...args) {
    return insert(pos, value_type(std::forward<Args>(args)...));
  }
  iterator erase(iterator pos) { return erase(pos, pos + 1); }
  iterator erase(iterator first, iterator last) {
    iterator new_finish = std::move(last, m_finish, first);
    // std::destroy(new_finish, m_finish);
    ezstl::destroy(new_finish, m_finish);
    m_finish = new_finish;
    return first;
  }
  void push_back(const value_type &value) { insert(end(), value); }
  void push_back(value_type &&value) { insert(end(), std::move(value)); }
  template <typename... Args>
  void emplace_back(Args &&...args) {
    push_back(value_type(std::forward<Args>(args)...));
  }
  // template <typename... Args>
  // reference emplace_bakc(Args &&...args);
  void pop_back() { erase(end() - 1); }
  void resize(size_type count) { resize(count, value_type{}); }
  void resize(size_type count, const value_type &value) {
    if (count == size()) return;
    if (count < size()) {
      // std::destroy(begin() + count, end());
      ezstl::destroy(begin() + count, end());
      m_finish = begin() + count;
    } else {
      size_type elems_over = count - size();
      if (capacity() - size() >= elems_over) {
        // std::destroy(begin(), end());
        ezstl::destroy(begin(), end());
        m_finish = std::uninitialized_fill_n(begin(), count, value);
      } else {
        size_type new_size = std::max(2 * size(), size() + elems_over);
        std::cout << elems_over << " " << new_size << std::endl;
        iterator new_start = allocate(new_size);
        iterator new_finish =
            std::uninitialized_move(m_start, m_finish, new_start);
        new_finish = std::uninitialized_fill_n(new_finish, elems_over, value);
        // std::destroy(begin(), end());
        ezstl::destroy(begin(), end());
        deallocate(m_start, capacity());
        m_start = new_start;
        m_finish = new_finish;
        m_end_of_storage = m_start + new_size;
      }
    }
  }
  void swap(Vector &other) {
    std::swap(m_start, other.m_start);
    std::swap(m_finish, other.m_finish);
    std::swap(m_end_of_storage, other.m_end_of_storage);
  }

 private:
  iterator allocate(size_type n) {
    // return static_cast<value_type *>(operator new(n * sizeof(value_type)));
    return Allocator::allocate(n);
  }

  void deallocate(iterator p, size_type n) {
    // operator delete(p);
    Allocator::deallocate(p, n);
  }

 private:
  value_type *m_start;
  value_type *m_finish;
  value_type *m_end_of_storage;
};

}  // namespace ezstl
